EVENTO
Teoria Espectral dos Grafos: uma área multidisciplinar
Tipo de evento: Seminário LNCC
A Teoria Espectral dos Grafo, TEG, teve origem em Química Quântica quando, em 1931, Huckel (1) produziu um modelo teórico para um problema, a partir de moléculas de hidrocarbonetos não saturadas, em que os níveis de energia de certos elétrons eram representados por autovalores de um grafo. No entanto, somente em 1957, com o artigo de Collatz e Sigogowitz (2), foi iniciada a fundamentação teórica de TEG, sedimentada em 1971, com a tese de doutorado de Cvetkovic (3). Até meados de 1980, cerca de 700 trabalhos já haviam sido publicados por pesquisadores matemáticos e químicos, tendo nesta época surgido o primeiro livro sobre este assunto, Spectra of Graphs: Theory and Application, devido a D. Cvetkovic, M. Doob e H. Sachs. Nas últimas duas décadas, o número de trabalhos científicos publicados sobre grafos espectrais tem crescido enormemente e a maioria deles aborda a relação entre a teoria espectral de matrizes e as propriedades estruturais dos grafos. Diversas técnicas espectrais para tratar problemas em grafos vêm sendo desenvolvidas, destacando-se os auto-espaços de grafos e a técnica do complementar de grafos estrela. Há muitas ligações entre TEG e diversos ramos da Combinatória, assim como, Álgebra e Geometria, podendo ser considerada um híbrido entre Álgebra Linear, Matemática Discreta, Combinatória e Teoria dos Grafos. TEG pode ser também classificada como parte da Teoria Algébrica dos Grafos e da Combinatória Algébrica. Diversas aplicações de TEG são encontradas em Química, Física, Biologia, Engenharia e Ciência da Computação. Nesta palestra serão apresentados alguns conceitos básicos de grafos espectrais e será mostrado como é possível utilizar resultados simples da Álgebra Linear para determinar propriedades em grafos, pelo relacionamento da estrutura do grafo e dos espectros de suas matrizes de adjacência e laplaciana. Serão também apresentados alguns conceitos de energia de grafos, muito úteis na Química e, finalmente, serão apontados futuros desenvolvimentos dessa área. (1) Huckel,E., Quantentheoretische Beitrage Zum Benzolproblem, Z. Phys. 70 (1931), 204-286.(2) Collatz e Sinogowitz, Spectren endlicher grafen, Abh. Math. Sem., Univer. Hamburg, 21 (1957), 63-77.(3) Cvetkovic, Graphs and their spectra, Univ. Beograd, Publ. Elektrotehn, Fak., Ser. Mat. Fiz., 354 (1971), 1-50.(4) Cvetkovic, D., Rowlinson, P., Simic, S., Eigenspaces of graphs, Encyclopedia of Mathematics and its Applications, 66, Cambridge, University Press (1997).(5) Erthal de Moraes, P., Abreu, N.M. M e Jurkiewicz, S., Graphs with homogeneous density in (a,b)-linear classes, Congr. Nume. 151 (2001) 53-64.(6) Oliveira, C. S., Abreu, N. M. M. e Jurkiewicz, S., The characteristic polynomial os the Laplacian of graphs in (a,b)-linear classes, Linear Algebra and its Applications 356 (2002) 113-121.(7) Oliveira, C. S., Abreu, N. M. M. e Pazoto, A. F., Sequence of Graphs and Vulnerability of Networks, apresentado em IV ALIO/ EURO Workshop on Applied Combinatorial Optimization, Nov. (2002), Pucón, Chile, a ser submetido à Discrete Applied Mathematics.
Data Início: 05/04/2005 Hora: 14:00 Data Fim: Hora: 15:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio B
Comitê Organizador: Nair Maria Maia de Abreu - Universidade Federal do Rio de Janeiro - COPPE/UFRJ - nair@pep.ufrj.br
